Vùng đất Nghệ An từ xa xưa đã là một trọng trấn của lãnh thổ Việt Nam. Từ thời Bắc thuộc, nhà Đường đã cho xây dựng phủ thành Hoan châu để trấn giữ phương Nam. Theo các nhà nghiên cứu hiện đại, năm 713, Mai Thúc Loan đã dựng cờ khởi nghĩa, đánh chiếm phủ thành Hoan châu,[2] từ đó kéo quân ra Bắc đánh hạ thành Tống Bình, giải phóng người Việt khỏi ách đô hộ của nhà Đường trong 10 năm.[3]

Thời kỳ độc lập, sách Đại Việt Sử ký toàn thư có chép sự kiện năm 1382, quân Chiêm Thành xâm lấn Đại Việt, bị quân nhà Trần đuổi đánh đến thành Nghệ An.[4] Sử liệu không cho biết vị trí cụ thể ngôi thành này. Có lẽ đây chính là thành Rùm, hay Lam thành (thuộc địa bàn xã Hưng Thành, huyện Hưng Nguyên ngày nay), do Hồ Quý Ly cho xây dựng để phòng thủ phía Nam.[5]

Lam thành được xây trên núi Thành. vòng thành chạy ôm từ sườn núi phía Đông Bắc xuống phía Nam rồi vòng lên phía Tây. Thành có hình thang, xây ghép bằng đá núi, vôi, mật, trên mặt thành có nhiều đoạn được xây cao làm vọng gác, ụ súng... Ngày nay, công trình chỉ còn lại một vài dấu dấu tích, không chỉ do thời gian tàn phá, mà còn bị xâm phạm ở các hoạt động đào bới đất đá, khai thác quặng trong thời gian dài.[5]

Khi quân Minh chiếm Đại Việt, Nghệ An được đổi làm phủ và Lam thành là trị sở của phủ Nghệ An.

Lam thành thường xuyên là mục tiên công hạ của nhà Hậu Trần để thiết lập căn cứ kháng Minh. Kể cả khi nhà Hậu Trần bị diệt, các các lực lượng kháng Minh của người Việt vẫn liên tục nổi dậy. Tháng 7 (âl) năm 1419, Phan Liêu[6], một quan viên người Việt được nhà Minh bổ làm Tri phủ Nghệ An, vì bị quan nhà Minh bức bách lấy vàng bạc, dẫn quân nổi dậy, bắt giết các quan cai trị do nhà Minh phái đến, rồi đem quân vây thành Nghệ An. Lúc sắp hạ được thành thì bị tổng binh Lý Bân đem quân tiếp việc đến. Phan Liêu phải trốn sang Ai Lao. Lý Bân truy bắt không kịp, bèn quay về Nghệ An, sửa sang lại Lam thành.[7][8]

Năm 1424, theo kế của Nguyễn Chích, thủ lĩnh nghĩa quân Lam Sơn là Lê Lợi đã quyết định đưa quân vào Nghệ An, hòng xây dựng địa bàn căn cứ chiến lược kháng Minh.[9] Quân Lam Sơn từng bước tiêu diệt các thành lũy trên đất Nghệ An, buộc quân Minh phải co cụm vào thành Nghệ An cố thủ. Các đại tướng của quân Minh gồm Trần Trí, Lý An, Phương Chính đều từng bị quân Lam Sơn vây khốn trong thành này.[10][11] Thành Nghệ An bị quân Lam Sơn vây khốn đến tháng 2(âl) năm 1427 thì tướng trấn thành là Thái Phúc, dưới sự khuyên nhủ của Nguyễn Trãi, đã nộp thành đầu hàng.[12][13]

Sang thời Lê, trị sở trấn Nghệ An dời về làng Dinh Cầu (nay thuộc xã Kỳ Châu, huyện Kỳ Anh, Hà Tĩnh), sau dời về Dũng Quyết (nay thuộc phường Trung Đô, thành phố Vinh, Nghệ An). Lam thành chỉ còn là lỵ sở của Thừa ty và Hiến ty của trấn Nghệ An.[14]

Sau khi lên ngôi, vua Quang Trung từng có ý định dời kinh đô từ Phú Xuân đến Nghệ An. Ông cho khảo sát để xây dựng tòa kinh thành mới và đặt tên là Phượng Hoàng trung đô. Vị trí của kinh thành được chọn nằm gần chân núi Quyết (tức gần như trùm lên thành cũ), kéo dài đến Rú Mèo. Thành có cấu trúc gồm 2 vòng thành gọi là thành Nội và thành Ngoại. Thành Ngoại có hình thang, chu vi 2.820 m, diện tích khoảng 22 ha, được đắp bằng đất. Phía ngoài thành có hào rộng 3 m, sâu 3 m, mặt thành cao 3–4 m. Thành Nội xây bằng gạch vồ và đá ong, chu vi gần 1.680 m, cao 2 m, cửa lớn mở ra hai hướng tây và đông. Trong thành Nội có toà lầu rộng, cao 3 tầng, trước có bậc tam cấp bằng đá ong, sau có hai dãy hành lang nối liền với điện Thái Hòa dùng cho việc thiết triều. Nhìn từ trên không thì Thành Nội gần như hình tam giác: mặt hành phía Đông Bắc chạy sát theo chân núi Quyết (Phượng Hoàng), phía Nam cắt ngang qua núi Mèo (Kỳ Lân), phía Tây kéo dài qua cánh đồng theo một đường thẳng lên sát Mũi Rồng (một nhánh của núi Dũng Quyết).[15]

Sách La Sơn phu tử nói rõ thêm:

Cũng theo sách La Sơn phu tử, về kích thước của thành Ngoại, ngoài các vách núi làm bức luỹ tự nhiên, còn phải đắp bờ thành nam dài 300 m, bờ thành tây dài 450 m. Bề đứng ở những đoạn phải đắp cũng rất cao vì để hài hoà với vách núi.[16]

Tuy nhiên, việc xây dựng thành Phượng Hoàng vấp phải sự phải đối của dân chúng do chính sách hà khắc của nhà Tây Sơn. Bên cạnh đó, vua Quang Trung cũng băng hà khi chưa kịp thực hiện việc dời đô. Thành Phượng Hoàng hoàn toàn bị bỏ phế.